package cn.lbd.datastructure;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Graph {
    //存放顶点集合
    private List<String> vertexes;
    //存放图对应的邻接矩阵
    private int[][] edges;
    //表示边的数目
    private int numsOfEdges;
    private boolean[] isVisited;

    public Graph(int n) {
        vertexes = new ArrayList<>(n);
        edges = new int[n][n];
        numsOfEdges = 0;
    }

    public static void main(String[] args) {
        int n = 5;
        String[] vertexes = {"A", "B", "C", "D", "E"};
        Graph graph = new Graph(n);

        for (int i = 0; i < n; i++) {
            graph.insertVertex(vertexes[i]);
        }

        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);

        System.out.println("邻接矩阵：");
        graph.showGraph();

       /* graph.dfs();*/

        graph.bfs();
    }

    /**
     * 得到第一个邻接结点的下标 w
     *
     * @param index 当前节点下标
     * @return
     */
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexes.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * //根据前一个邻接结点的下标来获取下一个邻接结点
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < vertexes.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 遍历所有节点，并进行DFS
     */
    public void dfs() {
        isVisited = new boolean[vertexes.size()];
        for (int i = 0; i < getNumsOfVertexes(); i++) {
            //回溯法
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }

    }

    /**
     * 对一个结点进行深度优先遍历的方法
     *
     * @param isVisited 记录节点是否被访问状态的数组
     * @param v         从哪个顶点开始访问
     */
    private void dfs(boolean[] isVisited, int v) {
        //访问当前节点 ==> 输出
        System.out.print(getValueByIndex(v) + "=>");
        //将当前顶点状态置为已访问
        isVisited[v] = true;
        //当前顶点的邻接点
        int w = getFirstNeighbor(v);
        while (w != -1) { //邻接点存在时
            //如果邻接点未被访问过
            if (!isVisited[w]) {
                //递归的搜索邻接点
                // 这里走到c时，ab都访问过了，while循环走完，函数开始出栈，递归开始返回值，回溯到c的前一个顶点b,如果b有其他的邻接点就继续递归的dfs，没有就回溯到a顶点
                dfs(isVisited, w);
            } else {
                //根据前一个邻接结点的下标来获取下一个邻接结点
                w = getNextNeighbor(v, w);
            }
        }
    }

    /**
     * 遍历所有的结点，都进行广度优先搜索
     */
    public void bfs() {
        isVisited = new boolean[getNumsOfVertexes()];
        for (int i = 0; i < getNumsOfVertexes(); i++) {
            if (!isVisited[i]){
                bfs(isVisited,i);
            }
        }
    }

    /**
     * 对一个结点进行广度优先遍历的方法
     *
     * @param isVisited 记录节点是否被访问状态的数组
     * @param v         从哪个顶点开始访问
     */
    private void bfs(boolean[] isVisited, int v) {
        int u; //队列出队节点所对应的下标
        int w; //邻接点w

        System.out.print(getValueByIndex(v) + "=>");
        LinkedList queue = new LinkedList();
        queue.addLast(v);
        isVisited[v] = true;
        while (!queue.isEmpty()){
            u =(Integer) queue.removeFirst();
            w = getFirstNeighbor(u);
            while (w != -1){
                if (!isVisited[w]){
                    System.out.print(getValueByIndex(w) + "=>");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u,w);
            }
        }
    }

    /**
     * 遍历图
     */
    public void showGraph() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }

    }

    /**
     * 获取图中顶点总数
     *
     * @return
     */
    public int getNumsOfVertexes() {
        return vertexes.size();
    }

    /**
     * 通过索引取得真正的数据
     *
     * @param index 顶点的下标
     * @return
     */
    public String getValueByIndex(int index) {
        return vertexes.get(index);
    }

    /**
     * 获得图中总边数
     *
     * @return
     */
    public int getNumsOfEdges() {
        return numsOfEdges;
    }

    /**
     * 获得权重
     *
     * @param v1 顶点1
     * @param v2 顶点2
     * @return
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 加入点
     *
     * @param vertex
     */
    public void insertVertex(String vertex) {
        vertexes.add(vertex);
    }

    /**
     * 加入边
     *
     * @param v1     顶点1
     * @param v2     顶点2
     * @param weight 权重
     */
    public void insertEdge(Integer v1, Integer v2, Integer weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numsOfEdges++;
    }
}
